Legacy:Insertion Sort

Insertion Sort is an iterative sorting algorithm like Bubble Sort. While this algorithm generally is less efficient than QuickSort, the UnrealScript implementation on this page can greatly out-perform QuickSort in certain cases. For more information, see Wikipedia:Insertion Sort.

Advantages of Insertion Sort

• Simple to implement
• Efficient on (quite) small data sets
• Efficient on data sets which are already substantially sorted
• Stable (i.e. does not change the order of already ordered elements)
• Does not suffer from poor "worst case input" performance
• Minimal memory requirements

Algorithm

Originally the Insertion Sort algorithm works like this:

1. Start with the result being the first element of the input.
2. Loop over the input array until it is empty, "removing" the first remaining (leftmost) element.
3. Compare the removed element against the current result, starting from the highest (rightmost) element and working left towards the lowest element.
4. If the removed input element is lower than the current result element, copy that value into the following element to make room for the new element below and repeat with the next lowest result element.
5. Otherwise, the new element is in the correct location; save it in the cell left by copying the last examined result up and start again from (2) with the next input element.

However, with UnrealScript's dynamic arrays and their Remove() and Insert() methods the algorithm can be modified to this:

1. Start with the result being the first element of the input.
2. Loop over the input array until it is empty, remembering the first remaining (leftmost) element.
3. Compare the removed element against the current result, starting from the highest (rightmost) element, and working left towards the lowest element.
4. If the removed input element is higher than the current result element, the element's correct location is found; remove it from its original location, insert it at the new location and start again from (2) with the next input element.

For numeric arrays the last two steps can be optimized using BinarySearch to search the new location in the sorted part of the array if it's not already in the correct location.

Code

Implementation for Dynamic Arrays of Strings

This implementation only works for dynamic arrays. This particular example sorts all elements in MyArray with an index between (including) the LowerBound and the UpperBound. Optionally it can sort the strings case-insensitively.

//== static InsertSortSArray ==================================================
/**
Sorts a string array using Insertion Sort.
Due to the dynamic array implementation this is considerably faster than
QuickSort on smaller arrays and especially on already sorted arrays.
*/
//=============================================================================
 
static final function InsertSortSArray(out array<string> MyArray, int LowerBound, int UpperBound, optional bool bCaseInsenstive)
{
  local int InsertIndex, RemovedIndex;
 
  if ( LowerBound < UpperBound )
     for (RemovedIndex = LowerBound + 1; RemovedIndex <= UpperBound; ++RemovedIndex) {
      InsertIndex = RemovedIndex;
      if ( !bCaseInsenstive ) {
        while (InsertIndex > LowerBound && MyArray[InsertIndex-1] > MyArray[RemovedIndex])
          --InsertIndex;
      }
      else {
        while (InsertIndex > LowerBound && Caps(MyArray[InsertIndex-1]) > Caps(MyArray[RemovedIndex]))
          --InsertIndex;
      }
      if ( RemovedIndex != InsertIndex ) {
        MyArray.Insert(InsertIndex, 1);
        MyArray[InsertIndex] = MyArray[RemovedIndex + 1];
        MyArray.Remove(RemovedIndex + 1, 1);
      }
    }
}

Foxpaw: Are you sure that that's an optimization, Wormbo? By removing the temporary variable, you save an assignment, but you gain two addition operations.

Wormbo: In UnrealScript assignments are very expensive operations, especially if you're not dealing with string, but e.g. complex structs. In that case it's really an optimization.

Optimized Implementation for Dynamic Arrays of Numeric Values

This implementation's use of BinarySearch for finding the InsertIndex of unsorted elements means a huge performance improvement over a linear search approach with large, unsorted arrays.

Also, because binary search requires less iterations for finding the InsertIndex, this implementation of Insertion Sort can handle larger unsorted arrays than the string implementation above without causing a runaway loop crash.

An extreme example: It took about 80 seconds (!) to sort a test array with 100,000 random integer numbers, but it was sorted without crashing. Sorting this huge sorted array again took only about 100 milliseconds.

You can use this implementation for any kind of dynamic array of comparable values.

//== static InsertSortIArray ==================================================
/**
Sorts an int array using optimized Insertion Sort.
This implementation outperforms QuickSort due to its use of dynamic arrays and
BinarySearch for unsorted elements.
*/
//=============================================================================
 
static final function InsertSortIArray(out array<int> MyArray, int LowerBound, int UpperBound)
{
  local int InsertIndex, RemovedIndex;
  local int High, Closest;
 
  if ( LowerBound < UpperBound )
     for (RemovedIndex = LowerBound + 1; RemovedIndex <= UpperBound; ++RemovedIndex) {
      if ( MyArray[RemovedIndex-1] > MyArray[RemovedIndex] ) {
        // element is not in the correct place, find InsertIndex with BinarySearch
        InsertIndex = 0;
        High = RemovedIndex - 1;
        while (InsertIndex <= High) {
          Closest = (InsertIndex + High) / 2;
          if ( MyArray[Closest] == MyArray[RemovedIndex] ) {
            InsertIndex = Closest;
            break;
          }
          if ( MyArray[Closest] > MyArray[RemovedIndex] )
            High = Closest - 1;
          else if ( MyArray[Closest] < MyArray[RemovedIndex] )
            InsertIndex = Closest + 1;
        }
        if ( InsertIndex < RemovedIndex && MyArray[InsertIndex] < MyArray[RemovedIndex] )
          ++InsertIndex;
      }
      else
        InsertIndex = RemovedIndex;
 
 
      if ( RemovedIndex != InsertIndex ) {
        MyArray.Insert(InsertIndex, 1);
        MyArray[InsertIndex] = MyArray[RemovedIndex + 1];
        MyArray.Remove(RemovedIndex + 1, 1);
      }
    }
}

Related Topics

• QuickSort
• BinarySearch
• Open Source